{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Add Bold Tag in String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #trie #array #hash-table #string #string-matching"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字典树 #数组 #哈希表 #字符串 #字符串匹配"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: addBoldTag"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #给字符串添加加粗标签"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定字符串 <code>s</code> 和字符串数组 <code>words</code>。</p>\n",
    "\n",
    "<p>对于 <code>s</code> 内部的子字符串，若其存在于 <code>words</code> 数组中， 则通过添加闭合的粗体标签<meta charset=\"UTF-8\" />&nbsp;<code>&lt;b&gt;</code>&nbsp;和&nbsp;<code>&lt;/b&gt;</code>&nbsp;进行加粗标记。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果两个这样的子字符串重叠，你应该仅使用一对闭合的粗体标签将它们包围起来。</li>\n",
    "\t<li>如果被粗体标签包围的两个子字符串是连续的，你应该将它们合并。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回添加加粗标签后的字符串 <code>s</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong> s = \"abcxyz123\", words = [\"abc\",\"123\"]\n",
    "<strong>输出：</strong>\"&lt;b&gt;abc&lt;/b&gt;xyz&lt;b&gt;123&lt;/b&gt;\"\n",
    "<strong>解释：</strong>两个单词字符串是 s 的子字符串，如下所示: \"abcxyz123\"。\n",
    "我们在每个子字符串之前添加&lt;b&gt;，在每个子字符串之后添加&lt;/b&gt;。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aaabbcc\", words = [\"aaa\",\"aab\",\"bc\"]\n",
    "<strong>输出：</strong>\"&lt;b&gt;aaabbc&lt;/b&gt;c\"\n",
    "<strong>解释：</strong>\n",
    "\"aa\"作为子字符串出现了两次: \"<u>aa</u>abbb\" 和 \"a<u>aa</u>bbb\"。\n",
    "\"b\"作为子字符串出现了三次: \"aaa<u>b</u>bb\"、\"aaab<u>b</u>b\" 和 \"aaabb<u>b</u>\"。\n",
    "我们在每个子字符串之前添加&lt;b&gt;，在每个子字符串之后添加&lt;/b&gt;: \"&lt;b&gt;a&lt;b&gt;a&lt;/b&gt;a&lt;/b&gt;&lt;b&gt;b&lt;/b&gt;&lt;b&gt;b&lt;/b&gt;&lt;b&gt;b&lt;/b&gt;\"。\n",
    "由于前两个&lt;b&gt;重叠，把它们合并得到: \"&lt;b&gt;aaa&lt;/b&gt;&lt;b&gt;b&lt;/b&gt;&lt;b&gt;b&lt;/b&gt;&lt;b&gt;b&lt;/b&gt;\"。\n",
    "由于现在这四个&lt;b&gt;是连续的，把它们合并得到: \"&lt;b&gt;aaabbb&lt;/b&gt;\"。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= words.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= words[i].length &lt;= 1000</code></li>\n",
    "\t<li><code>s</code> 和 <code>words[i]</code> 由英文字母和数字组成</li>\n",
    "\t<li><code>words</code> 中的所有值 <strong>互不相同</strong></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注：</strong>此题与「758 - 字符串中的加粗单词」相同 - <a href=\"https://leetcode-cn.com/problems/bold-words-in-string\">https://leetcode-cn.com/problems/bold-words-in-string</a></p>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [add-bold-tag-in-string](https://leetcode.cn/problems/add-bold-tag-in-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [add-bold-tag-in-string](https://leetcode.cn/problems/add-bold-tag-in-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abcxyz123\"\\n[\"abc\",\"123\"]', '\"aaabbb\"\\n[\"aa\",\"b\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        s_len = len(s)\n",
    "        mask = [False for i in range(s_len)]\n",
    "\n",
    "        for index in range(s_len):\n",
    "            for word in words:\n",
    "                word_len = len(word)\n",
    "                if index + word_len <= s_len and s[index: word_len + index] == word:\n",
    "                    for j in range(index, index + word_len):\n",
    "                        mask[j] = True\n",
    "\n",
    "        res = []\n",
    "\n",
    "        for index in range(s_len):\n",
    "            if mask[index] and (index == 0 or not mask[index - 1]):\n",
    "                res.append(\"<b>\")\n",
    "            res.append(s[index])\n",
    "            if mask[index] and (index == s_len - 1 or not mask[index + 1]):\n",
    "                res.append(\"</b>\")\n",
    "\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        # list_s = list(s)\n",
    "        # dic = defaultdict(list)\n",
    "        # for w in words:\n",
    "        #     dic[w] = [i for i in range(len(s)) if \"\".join(list_s[i:i+len(w)]) == w]\n",
    "        #     # print(dic[w])\n",
    "        #     dic[w].append(dic[w][0]+len(w))\n",
    "        # print(dic)\n",
    "        N = len(s)\n",
    "        mask = [False] *N\n",
    "        for i in range(N):\n",
    "            prefix = s[i:]\n",
    "            for word in words:\n",
    "                if prefix.startswith(word):\n",
    "                    for j in range(i,min(i+len(word), N)):\n",
    "                        mask[j] = True\n",
    "        ans = []\n",
    "        for i in range(N):\n",
    "            if mask[i] and (i==0 or not mask[i-1]):\n",
    "                ans.append('<b>')\n",
    "            ans.append(s[i])\n",
    "            if mask[i] and (i==N-1 or not mask[i+1]):\n",
    "                ans.append('</b>')\n",
    "        return \"\".join(ans)  \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 枚举法\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "      n = len(s)\n",
    "      mask = [False] * n\n",
    "      for i in range(n):\n",
    "        prefix = s[i:]\n",
    "        for word in words:\n",
    "          if prefix.startswith(word):\n",
    "            for j in range(i, min(i+len(word), n)):\n",
    "              mask[j] = True\n",
    "      \n",
    "      res = []\n",
    "      # groupby支持两个参数，第一个参数是需要迭代的对象，第二个函数key代表分组依据，如果为none则表示使用迭代对象中的元素作为分组依据\n",
    "      for incl, grp in itertools.groupby(zip(s, mask), lambda z: z[1]):\n",
    "        if incl: res.append('<b>')\n",
    "        res.append(''.join(z[0] for z in grp))\n",
    "        if incl: res.append('</b>')\n",
    "      return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        site = []\n",
    "        for i in range(len(s)):\n",
    "            for word in words:\n",
    "                if s[i:i + len(word)] == word:\n",
    "                    a = i\n",
    "                    b = i + len(word)\n",
    "                    if site and site[-1][-1] >= a:\n",
    "                        site[-1][-1] = max(b, site[-1][-1])\n",
    "                    else:\n",
    "                        site.append([a, b])\n",
    "        ans = ''\n",
    "        i = 0\n",
    "        n = len(s)\n",
    "        now = 0\n",
    "        while i < n:\n",
    "            if now < len(site) and i == site[now][0]:\n",
    "                ans += '<b>' + s[i:site[now][1]] + '</b>'\n",
    "                i = site[now][1]\n",
    "                now += 1\n",
    "            else:\n",
    "                ans += s[i]\n",
    "                i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        s_len = len(s)\n",
    "        mask = [False for i in range(s_len)]\n",
    "\n",
    "        for index in range(s_len):\n",
    "            for word in words:\n",
    "                word_len = len(word)\n",
    "                if   s[index: word_len + index] == word:\n",
    "                    for j in range(index, index + word_len):\n",
    "                        mask[j] = True\n",
    "\n",
    "        res = []\n",
    "\n",
    "        for index in range(s_len):\n",
    "            if mask[index] and (index == 0 or not mask[index - 1]):\n",
    "                res.append(\"<b>\")\n",
    "            res.append(s[index])\n",
    "            if mask[index] and (index == s_len - 1 or not mask[index + 1]):\n",
    "                res.append(\"</b>\")\n",
    "\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        n = len(s)\n",
    "\n",
    "        mask = [False] * n\n",
    "\n",
    "        for idx in range(n):\n",
    "            for word in words:\n",
    "                wl = len(word)\n",
    "                if s[idx: idx+wl] == word:\n",
    "                    for i in range(idx, idx+wl):\n",
    "                        mask[i] = True\n",
    "        \n",
    "        res = ''\n",
    "        match = False\n",
    "        for i, v in enumerate(mask):\n",
    "            if v and not match:\n",
    "                res += '<b>'\n",
    "                match = True\n",
    "            \n",
    "            elif not v and match:\n",
    "                res += '</b>'\n",
    "                match = False\n",
    "            \n",
    "            res += s[i]\n",
    "        \n",
    "        if match:\n",
    "            res += '</b>'\n",
    "        \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        n = len(s)\n",
    "        mask = [False] * n\n",
    "        end = 0\n",
    "        for i in range(n):\n",
    "            for word in words:\n",
    "                if s[i:].startswith(word):\n",
    "                    end = max(end, i + len(word))\n",
    "            if i < end:\n",
    "                mask[i] = True\n",
    "        ans = \"\"\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if mask[i]:\n",
    "                j = i\n",
    "                while j < n and mask[j]:\n",
    "                    j += 1\n",
    "                ans += \"<b>\" + s[i:j] + \"</b>\"\n",
    "                i = j\n",
    "            else:\n",
    "                ans += s[i]\n",
    "                i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        n = len(s)\n",
    "        mask = [False]*n\n",
    "\n",
    "        for i in range(n):\n",
    "            for x in words:\n",
    "                if i + len(x) <= n and s[i:i + len(x)] == x:\n",
    "                    for j in range(i,i + len(x)):\n",
    "                        mask[j] = True\n",
    "        ans = ''\n",
    "        for i in range(n):\n",
    "            if mask[i] and (i == 0 or mask[i - 1] == False):\n",
    "                ans += '<b>'\n",
    "            ans += s[i]\n",
    "\n",
    "            if mask[i] and (i == n - 1 or mask[i + 1] == False):\n",
    "                ans += '</b>'\n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        mask = [0] * len(s)\n",
    "        for i in range(len(s)):\n",
    "            for word in words:\n",
    "                if s[i:].startswith(word):\n",
    "                    mask[i:i+len(word)] = [1] * len(word)\n",
    "        res = \"\"\n",
    "        for i in range(len(s)):\n",
    "            if mask[i] == 1 and (i == 0 or mask[i - 1] == 0):\n",
    "                res += \"<b>\"\n",
    "            res += s[i]\n",
    "            if mask[i] == 1 and (i == len(s) - 1 or mask[i + 1] == 0):\n",
    "                res += \"</b>\"\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        # time complexity: O(n + w * n^2 + n) \n",
    "        # space complexity: O(n)\n",
    "\n",
    "        \"\"\"\n",
    "        首先，我们可以为字符串s中的每个字符标记一个布尔值，指示该字符是否需要加粗\n",
    "        使用一次遍历来确定需要加粗的范围\n",
    "\n",
    "        \"\"\"\n",
    "        n = len(s)\n",
    "        bold = [False] * n\n",
    "\n",
    "        for word in words:\n",
    "            index = 0\n",
    "            while index < n:\n",
    "                start = s.find(word, index)\n",
    "                if start == -1:\n",
    "                    break\n",
    "                \n",
    "                end = start + len(word)\n",
    "\n",
    "                for i in range(start, end):\n",
    "                    bold[i] = True\n",
    "                index += 1\n",
    "\n",
    "\n",
    "        result = []\n",
    "        for i in range(n):\n",
    "            if bold[i] and (i == 0 or not bold[i - 1]):\n",
    "                result.append(\"<b>\")\n",
    "            result.append(s[i])\n",
    "            if bold[i] and (i == n - 1 or not bold[i + 1]):\n",
    "                result.append(\"</b>\")\n",
    "        \n",
    "        return \"\".join(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        intervals = []\n",
    "        for i in range(len(s)):\n",
    "            for w in words:\n",
    "                if s[i:len(w) + i] == w:\n",
    "                    if intervals:\n",
    "                        l, r = intervals[-1]\n",
    "                        if i <= r + 1:\n",
    "                            intervals[-1][1] = max(len(w)+i-1, r)\n",
    "                            break\n",
    "                    intervals.append([i, len(w)+i-1])\n",
    "        res = ''\n",
    "        i = j = 0\n",
    "        while i < len(s):\n",
    "            if j < len(intervals):\n",
    "                l, r = intervals[j]\n",
    "                if i < l:\n",
    "                    res += s[i]\n",
    "                    i +=1\n",
    "                else:\n",
    "                    res += '<b>' + s[i:r + 1] + '</b>'\n",
    "                    i = r + 1\n",
    "                    j +=1\n",
    "            else:\n",
    "                res += s[i:]\n",
    "                break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        n = len(s)\n",
    "        mask = [False] * n\n",
    "        for i in range(n):\n",
    "            prefix = s[i:]\n",
    "            for word in words:\n",
    "                if prefix.startswith(word):\n",
    "                    for j in range(len(word)):\n",
    "                        mask[i+j] = True\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            m = mask[i]\n",
    "            pre = mask[i-1] if i > 0 else False\n",
    "            after = mask[i+1] if i + 1 < n else False\n",
    "            if not pre and m:\n",
    "                ans.append('<b>')\n",
    "            ans.append(s[i])\n",
    "            if not after and m:\n",
    "                ans.append('</b>')\n",
    "        return \"\".join(ans)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        n=len(s)\n",
    "        mask=[False]*n\n",
    "        for word in words:\n",
    "            for i in range(n-len(word)+1):\n",
    "                if s[i:i+len(word)]==word:\n",
    "                    #修改mask,有点差分的味道\n",
    "                    mask[i:i+len(word)]=[True]*len(word)\n",
    "        res=[]\n",
    "        for i in range(n):\n",
    "            if mask[i] and (i==0 or not mask[i-1]):\n",
    "                res.append(\"<b>\")\n",
    "            res.append(s[i])\n",
    "            if mask[i] and (i==n-1 or not mask[i+1]):\n",
    "                res.append(\"</b>\")\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        n=len(s)\n",
    "        mask=[False]*n\n",
    "        for word in words:\n",
    "            for i in range(n-len(word)+1):\n",
    "                if s[i:i+len(word)]==word:\n",
    "                    #修改mask,有点差分的味道\n",
    "                    mask[i:i+len(word)]=[True]*len(word)\n",
    "        res=[]\n",
    "        for i in range(n):\n",
    "            if mask[i] and (i==0 or not mask[i-1]):\n",
    "                res.append(\"<b>\")\n",
    "            res.append(s[i])\n",
    "            if mask[i] and (i==n-1 or not mask[i+1]):\n",
    "                res.append(\"</b>\")\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "\n",
    "        bolded = [False] * len(s)\n",
    "\n",
    "        for word in words:\n",
    "            start = s.find(word)\n",
    "            while start != -1:\n",
    "                for i in range(start, start + len(word)):\n",
    "                    bolded[i] = True\n",
    "                start = s.find(word, start + 1)\n",
    "\n",
    "        ans = []\n",
    "        for i, char in enumerate(s):\n",
    "            if bolded[i] and (i == 0 or not bolded[i - 1]):\n",
    "                ans.append(\"<b>\")\n",
    "            ans.append(char)\n",
    "            if bolded[i] and (i == len(s) - 1 or not bolded[i + 1]):\n",
    "                ans.append(\"</b>\")\n",
    "\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        mask = [False] * len(s)\n",
    "\n",
    "        for word in words:\n",
    "            start = s.find(word)\n",
    "            while start != -1:\n",
    "                for i in range(start, start + len(word)):\n",
    "                    mask[i] = True\n",
    "                start = s.find(word, start + 1)\n",
    "        \n",
    "        result = []\n",
    "        for i in range(len(s)):\n",
    "            if mask[i] and (i == 0 or not mask[i - 1]):\n",
    "                result.append('<b>')\n",
    "            result.append(s[i])\n",
    "            if mask[i] and (i == len(s) - 1 or not mask[i + 1]):\n",
    "                result.append('</b>')\n",
    "        \n",
    "        return ''.join(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        N = len(s) \n",
    "        mask = [False for _ in range(N)]\n",
    "        for i in range(N):\n",
    "            prefix = s[i:]\n",
    "            for word in words:\n",
    "                if prefix.startswith(word):\n",
    "                    for j in range(i, min(i+len(word), N)):\n",
    "                        mask[j] = True\n",
    "        ans = \"\"\n",
    "        for i in range(N):\n",
    "            if mask[i]==1 and (i==0 or mask[i-1]==0):\n",
    "                ans +=\"<b>\"\n",
    "            ans += s[i]\n",
    "            if mask[i]==1 and (i==N-1 or mask[i+1]==0):\n",
    "                ans+= \"</b>\"\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        n = len(s)\n",
    "        memo = [0] * (n+2)\n",
    "        for word in words:\n",
    "            curLen = len(word)\n",
    "            start = 0\n",
    "            while start < n:\n",
    "                tmp = s.find(word,start)\n",
    "                if tmp == -1:\n",
    "                    break\n",
    "                else:\n",
    "                    memo[tmp+1] += 1\n",
    "                    memo[tmp+curLen+1] -= 1\n",
    "                    start = tmp + 1\n",
    "        for i in range(1,n+1):\n",
    "            memo[i] = memo[i] + memo[i-1]\n",
    "        print(memo)\n",
    "        res = \"\"\n",
    "        find = False\n",
    "        for i in range(n):\n",
    "            if find == False:\n",
    "                if memo[i+1] > 0:\n",
    "                    find = True\n",
    "                    res += \"<b>\"\n",
    "                res += s[i]\n",
    "            else:\n",
    "                if memo[i+1] == 0:\n",
    "                    find = False\n",
    "                    res += \"</b>\"\n",
    "                res += s[i]\n",
    "        if find:\n",
    "            res += \"</b>\"\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        n = len(s)\n",
    "        b = [False]*n\n",
    "        for i in range(n):\n",
    "            prefix = s[i:]\n",
    "            max_len = 0\n",
    "            for word in words:\n",
    "                if prefix.startswith(word): max_len = max(max_len,len(word))\n",
    "            b[i:i+max_len] = [True]*max_len\n",
    "        \n",
    "        res = \"\"\n",
    "        for i in range(n):\n",
    "            if b[i]==True and (i==0 or b[i-1]==False): res+=\"<b>\"\n",
    "            res+=s[i]\n",
    "            if b[i]==True and (i==n-1 or b[i+1]==False): res+=\"</b>\"\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        result, p, prev = '', [0] * (len(s)+1), 0\n",
    "        for w in words:\n",
    "            i, n = s.find(w), len(w)\n",
    "            while i >= 0:\n",
    "                p[i] += 1\n",
    "                p[i+n] -= 1\n",
    "                i = s.find(w, i+1)\n",
    "        for c, x in zip_longest(s, accumulate(p), fillvalue=''):\n",
    "            if x and not prev:\n",
    "                result += '<b>'\n",
    "            elif not x and prev:\n",
    "                result += '</b>'\n",
    "            result += c\n",
    "            prev = x\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        n = len(s)\n",
    "        mask = [0] * n\n",
    "        for i in range(n):\n",
    "            for word in words:\n",
    "                if s[i:].startswith(word):\n",
    "                    for j in range(i, i+len(word)):\n",
    "                        mask[j] = 1\n",
    "        \n",
    "        res = ''\n",
    "        start = False\n",
    "        for i in range(n):\n",
    "            if mask[i]:\n",
    "                if start:\n",
    "                    res += s[i]\n",
    "                else:\n",
    "                    start = True\n",
    "                    res += '<b>' + s[i]\n",
    "            else:\n",
    "                if start:\n",
    "                    res += '</b>'\n",
    "                    start = False\n",
    "                res += s[i]\n",
    "        if start:\n",
    "            res += '</b>'\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        mask = [False] * len(s)\n",
    "        for word in words:\n",
    "            for i in range(len(s)):\n",
    "                if s[i:].startswith(word):\n",
    "                    mask[i: i+len(word)] = [True] * len(word)\n",
    "        \n",
    "        res = \"\"\n",
    "        for i in range(len(s)):\n",
    "            if mask[i] and (i==0 or mask[i-1]==False):\n",
    "                res += \"<b>\"\n",
    "            res += s[i]\n",
    "            if mask[i] and (i==len(s)-1 or mask[i+1]==False):\n",
    "                res += \"</b>\"\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        inter =[]\n",
    "        for i in range(0, len(s)):\n",
    "            for j in range(0,i+1):\n",
    "                if s[j:i+1] in words:\n",
    "                    inter.append((j,i))\n",
    "                    break\n",
    "\n",
    "        i = 1\n",
    "        while len(inter) > i:\n",
    "            flag = -1\n",
    "            for j in range(0, i):\n",
    "                if inter[i][0] <= inter[j][1]:\n",
    "                    if inter[i][0] > inter[j][0]:\n",
    "                        inter = inter[:j] + [(inter[j][0], inter[i][1])] + inter[i+1:]\n",
    "                    else:\n",
    "                        inter = inter[:j] + [(inter[i][0], inter[i][1])] + inter[i+1:]\n",
    "                    i = j+1\n",
    "                    flag = 1\n",
    "                    break\n",
    "            if flag == -1: i+=1\n",
    "\n",
    "        i = 1\n",
    "        while len(inter) > i:\n",
    "            if inter[i][0]-inter[i-1][1] == 1:\n",
    "                inter = inter[:i-1] + [(inter[i-1][0], inter[i][1])] + inter[i+1:]\n",
    "                continue\n",
    "            i+=1\n",
    "\n",
    "        i , j = 0,0\n",
    "        res = []\n",
    "        for cur in range(0, len(s)):\n",
    "            if i< len(inter) and cur == inter[i][0]:\n",
    "                if len(res) > 0 and res[-1] == \"</b>\":\n",
    "                    res = res[:-1] + [s[cur]]\n",
    "                else:\n",
    "                    res = res + [\"<b>\" ,s[cur]]\n",
    "                i +=1\n",
    "                if j < len(inter) and cur == inter[j][1]:\n",
    "                    res = res + [\"</b>\"]\n",
    "                    j +=1\n",
    "            elif j < len(inter) and cur == inter[j][1]:\n",
    "                res = res + [s[cur] , \"</b>\"]\n",
    "                j +=1\n",
    "            else:\n",
    "                res = res + [s[cur]]\n",
    "        \n",
    "        return \"\".join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        mark = [0] * len(s)\n",
    "        res = []\n",
    "        for word in words:\n",
    "            for i in range(len(word)-1, len(s)):\n",
    "                if word == s[i-len(word)+1: i+1]:\n",
    "                    mark[i-len(word)+1: i+1] = [1 for x in range(len(word))]\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i < len(mark):\n",
    "            if mark[i] == 1:\n",
    "                res.append(s[j:i])\n",
    "                res.append('<b>')\n",
    "                j = i + 1\n",
    "                while j < len(mark) and mark[j] == 1:\n",
    "                    j += 1\n",
    "                res.append(s[i: j])\n",
    "                res.append('</b>')\n",
    "                i = j - 1\n",
    "            i += 1\n",
    "        res.append(s[j:])\n",
    "        return \"\".join(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        n = len(s)\n",
    "        mask = [0] * n\n",
    "        for i in range(n):\n",
    "            prefix = s[i:]\n",
    "            for word in words:\n",
    "                if prefix.startswith(word):\n",
    "                    for j in range(i, min(i + len(word), n)):\n",
    "                        mask[j] = 1\n",
    "        ans = []\n",
    "        for incl, group in itertools.groupby(zip(s, mask), lambda z : z[1]):\n",
    "            if incl == 1:\n",
    "                ans.append('<b>')\n",
    "            ans.append(''.join(z[0] for z in group))\n",
    "            if incl == 1:\n",
    "                ans.append('</b>')\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        n = len(s)\n",
    "        bold = [False] * n\n",
    "        # iterate through every index position of string\n",
    "        # for every index position, iterate through every word to check if it is a prefix of current substring, if so, mark is as bolded\n",
    "        for i in range(n):\n",
    "            for w in words:\n",
    "                if s[i:].startswith(w):\n",
    "                    bold[i:i+len(w)] = [True] * len(w)\n",
    "        # combine all the bolded booleans into bold tags\n",
    "        res = \"\"\n",
    "        for i in range(n):\n",
    "            # current position is the start of bold\n",
    "            if bold[i] and (i == 0 or not bold[i-1]):\n",
    "                res += \"<b>\"\n",
    "            res += s[i]\n",
    "            # current position is the end of bold\n",
    "            if bold[i] and (i == n-1 or not bold[i+1]):\n",
    "                res += \"</b>\"\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        N = len(s)\n",
    "        mask = [False] * N\n",
    "        for i in range(N):\n",
    "            prefix = s[i:]\n",
    "            for word in words:\n",
    "                if prefix.startswith(word):\n",
    "                    for j in range(i, min(i+len(word), N)):\n",
    "                        mask[j] = True \n",
    "        \n",
    "        ans = []\n",
    "        for incl, grp in itertools.groupby(zip(s, mask), lambda z: z[1]):\n",
    "            if incl: ans.append(\"<b>\")\n",
    "            \n",
    "            ans.append(\"\".join(z[0] for z in grp))\n",
    "            if incl: ans.append(\"</b>\")\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        intervals = []\n",
    "        for i in range(len(s)):\n",
    "            for w in words:\n",
    "                if s[i:len(w) + i] == w:\n",
    "                    if intervals:\n",
    "                        l, r = intervals[-1]\n",
    "                        if i <= r + 1:\n",
    "                            intervals[-1][1] = max(len(w)+i-1, r)\n",
    "                            break\n",
    "                    intervals.append([i, len(w)+i-1])\n",
    "        \n",
    "        res = ''\n",
    "        i = j = 0\n",
    "        while i < len(s):\n",
    "            if j < len(intervals):\n",
    "                l,r = intervals[j]\n",
    "                if i < l:\n",
    "                    res += s[i]\n",
    "                    i += 1\n",
    "                else:\n",
    "                    res += '<b>' + s[i : r+1] + '</b>'\n",
    "                    i = r + 1\n",
    "                    j += 1\n",
    "            else:\n",
    "                res += s[i:]\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        n = len(s)\n",
    "        mask = [0] * n \n",
    "        for i in range(n):\n",
    "            for word in words:\n",
    "                if s[i:].startswith(word):\n",
    "                    mask[i:i + len(word)] = [1] * len(word)\n",
    "        \n",
    "        ans = ''\n",
    "        for i in range(n):\n",
    "            if mask[i] == 1 and (i == 0 or mask[i - 1] == 0):\n",
    "                ans += '<b>'\n",
    "            ans += s[i]\n",
    "            if mask[i] == 1 and (i == n - 1 or mask[i + 1] == 0):\n",
    "                ans += '</b>'\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        n = len(s)\n",
    "        mask = [0] * n\n",
    "        for i in range(n):\n",
    "            for word in words:\n",
    "                if s[i:].startswith(word):\n",
    "                    mask[i:i+len(word)] = [1] * len(word)\n",
    "        res = \"\"\n",
    "        for i in range(n):\n",
    "            if mask[i] == 1 and (i==0 or mask[i-1] == 0):\n",
    "                res += \"<b>\"\n",
    "            res += s[i]\n",
    "            if mask[i] == 1 and (i==n-1 or mask[i+1] == 0):\n",
    "                res += \"</b>\"\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        #区间性判断+模拟\n",
    "        n=len(s)\n",
    "        mask=[False]*n\n",
    "        for word in words:\n",
    "            for i in range(n-len(word)+1):\n",
    "                if s[i:i+len(word)]==word:\n",
    "                    #修改mask,有点差分的味道\n",
    "                    mask[i:i+len(word)]=[True]*len(word)\n",
    "        res=[]\n",
    "        for i in range(n):\n",
    "            if mask[i] and (i==0 or not mask[i-1]):\n",
    "                res.append(\"<b>\")\n",
    "            res.append(s[i])\n",
    "            if mask[i] and (i==n-1 or not mask[i+1]):\n",
    "                res.append(\"</b>\")\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "\n",
    "        starts = [0 for i in range(len(s) + 1)]\n",
    "\n",
    "        def helper(a):\n",
    "            return a[0], -a[1]\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            for w in words:\n",
    "                if i + len(w) <= len(s) and s[i:i+len(w)] == w:\n",
    "                    starts[i] += 1\n",
    "                    starts[i + len(w)] -= 1\n",
    "        \n",
    "        res = \"\"\n",
    "        cur = 0\n",
    "        \n",
    "        i = 0\n",
    "\n",
    "        for i in range(len(starts)):\n",
    "            start = starts[i]\n",
    "            if cur == 0 and start > 0:\n",
    "                res += \"<b>\"\n",
    "            cur += start\n",
    "            if cur == 0 and start < 0:\n",
    "                res += \"</b>\"\n",
    "            if i < len(s):\n",
    "                res += s[i] \n",
    "            \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        mark=[False]*len(s)\n",
    "        for i in words:\n",
    "            cursor=s.find(i)\n",
    "            while cursor!=-1:\n",
    "                for j in range(cursor,cursor+len(i)):\n",
    "                    mark[j]=True\n",
    "                cursor=s.find(i,cursor+1)\n",
    "        print(mark)\n",
    "        lis=''\n",
    "        for i in range(len(mark)):\n",
    "            if i==0 and mark[0]==True:\n",
    "                lis+='<b>'\n",
    "            if i>0 and mark[i]==True and mark[i-1]==False:\n",
    "                lis+='<b>'\n",
    "            lis+=s[i]\n",
    "            if i==len(s)-1 and mark[i]==True:\n",
    "                lis+='</b>'\n",
    "            if i<len(s)-1 and mark[i]==True and mark[i+1]==False:\n",
    "                lis+='</b>'\n",
    "        return lis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        mask = [False] * len(s)\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            tmp = s[i:]\n",
    "            for word in words:\n",
    "                if tmp.startswith(word):\n",
    "                    for j in range(i, i + len(word)):\n",
    "                        mask[j] = True\n",
    "        print(mask)\n",
    "        res = []\n",
    "        for flag, pieces in itertools.groupby(zip(s, mask), lambda x: x[1]):\n",
    "            if flag:\n",
    "                res.append('<b>')\n",
    "            res.append(''.join(x[0] for x in pieces))\n",
    "            if flag:\n",
    "                res.append('</b>')\n",
    "            print(res)\n",
    "        res = ''.join(res)\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        s_len = [0 for i in range(len(s))]\n",
    "        # print(s_len)\n",
    "        for word in words:\n",
    "            print(word)\n",
    "            pos = 0\n",
    "            pos_list = []\n",
    "            while pos!=len(s):\n",
    "                p = s[pos:].find(word)\n",
    "                if p==-1:\n",
    "                    break\n",
    "                for i in range(len(word)):\n",
    "                    s_len[pos+p+i] = 1\n",
    "                pos = p+pos+1\n",
    "        print(s_len)\n",
    "        result = \"\"\n",
    "        for i in range(len(s_len)):\n",
    "            if (i==0 and s_len[i]==1 and s_len[i+1]==0) or (i>0 and s_len[i-1]==0 and s_len[i]==1 and s_len[i+1]==0) or (i==len(s_len)-1 and s_len[i]==1 and s_len[i-1]==0):\n",
    "                result += \"<b>\"\n",
    "                result += s[i]\n",
    "                result += \"</b>\"\n",
    "            elif (i==0 and s_len[i]==1) or (i>0 and s_len[i-1]==0 and s_len[i]==1):\n",
    "                result += \"<b>\"\n",
    "                result += s[i]\n",
    "            elif (i==len(s_len)-1 and s_len[i]==1) or (i<len(s_len)-1 and s_len[i+1]==0 and s_len[i]==1):\n",
    "                result += s[i]\n",
    "                result += \"</b>\"\n",
    "            else:\n",
    "                result += s[i]\n",
    "        \n",
    "        print(result)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        begin = []\n",
    "        end = []\n",
    "        for word in words:\n",
    "            indices = [i for i in range(len(s)) if s.startswith(word, i)]\n",
    "            for start in indices:\n",
    "                begin.append(start)\n",
    "                end.append(start + len(word))\n",
    "        if not begin:\n",
    "            return s\n",
    "        \n",
    "        begin.sort()\n",
    "        end.sort()\n",
    "        # print(begin)\n",
    "        # print(end)\n",
    "\n",
    "        res_interv = []\n",
    "        # merge interv\n",
    "        left, right = begin[0], end[0]\n",
    "        for i in range(1, len(begin)):\n",
    "            if begin[i] <= right:\n",
    "                right = end[i]\n",
    "            else:\n",
    "                res_interv.append([left, right])\n",
    "                # reset \n",
    "                left, right = begin[i], end[i]\n",
    "        res_interv.append([left, right])\n",
    "        #print(res_interv)\n",
    "\n",
    "        # add special token\n",
    "        i = 0\n",
    "        res_str = \"\"\n",
    "        for interv in res_interv:\n",
    "            while i < interv[0]:\n",
    "                res_str += s[i]\n",
    "                i += 1\n",
    "            res_str += '<b>'\n",
    "            sub_len = interv[1] - interv[0]\n",
    "            while sub_len:\n",
    "                res_str += s[i]\n",
    "                sub_len -= 1\n",
    "                i += 1\n",
    "            res_str += '</b>'\n",
    "        # add tail\n",
    "        while i < len(s):\n",
    "            res_str += s[i]\n",
    "            i += 1\n",
    "\n",
    "        return res_str"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        stack = []\n",
    "        n = len(s)\n",
    "        words = set(words)\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                if s[i:j+1] in words:\n",
    "                    stack.append([i, j])\n",
    "        # print(stack)\n",
    "        final = []\n",
    "        for nums in stack:\n",
    "            if not final or nums[0] > final[-1][1]+1:\n",
    "                final.append(nums)\n",
    "            else:\n",
    "                temp = final.pop()\n",
    "                final.append([temp[0], max(temp[1], nums[1])])\n",
    "        # print(final)\n",
    "        res = ''\n",
    "        pre = 0\n",
    "        for index in final:\n",
    "            res += s[pre:index[0]]\n",
    "            res += '<b>'\n",
    "            res += s[index[0]:index[1]+1]\n",
    "            res += '</b>'\n",
    "            pre = index[1]+1\n",
    "        return res+s[pre:n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        word_list=[]\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i+1,len(s)+1):\n",
    "                if s[i:j] in words:\n",
    "                    word_list.append([i,j-1])\n",
    "        #区间合并\n",
    "        word_list.sort(key=lambda x:x[0])\n",
    "        print(word_list)\n",
    "        result=[]\n",
    "        if len(word_list)>0:\n",
    "            result.append(word_list[0])\n",
    "        for i in range(1,len(word_list)):\n",
    "            if result[-1][1]>=word_list[i][0]-1:\n",
    "                # print(max(result[-1][1],word_list[i][1]))\n",
    "                result[-1][1]=max(result[-1][1],word_list[i][1])\n",
    "            else:\n",
    "                result.append(word_list[i])\n",
    "        print(result)\n",
    "        count=0\n",
    "        result_str=\"\"\n",
    "        cur=0\n",
    "        while count<len(s):\n",
    "            if cur<len(result) and count==result[cur][0]:\n",
    "                result_str+=\"<b>\"+s[result[cur][0]:result[cur][1]+1]+\"</b>\"\n",
    "                count= result[cur][1]+1\n",
    "                cur+=1\n",
    "\n",
    "            else:\n",
    "                result_str+=s[count]\n",
    "                count+=1\n",
    "        return result_str\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        word_set = set(words)\n",
    "        n = len(s)\n",
    "        lst = []\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                if s[i:j+1] in word_set:\n",
    "                    lst.append([i, j])\n",
    "        ans = []\n",
    "        for interval in lst:\n",
    "            if not ans or interval[0] > ans[-1][1] + 1:\n",
    "                ans.append(interval)\n",
    "            else:\n",
    "                ans[-1][1] = max(ans[-1][1], interval[1])\n",
    "        starts = set(x[0] for x in ans)\n",
    "        ends = set(x[1] for x in ans)\n",
    "        print(ans)\n",
    "        res = \"\"\n",
    "        for i in range(len(s)):\n",
    "            if i in starts:\n",
    "                res += \"<b>\"\n",
    "            res += s[i]\n",
    "            if i in ends:\n",
    "                res += \"</b>\"\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        len_w = set([len(w) for w in words])\n",
    "        if not words:\n",
    "            return s\n",
    "        words = set(words)\n",
    "\n",
    "        len_s = len(s)\n",
    "        intervals = []\n",
    "\n",
    "        for i in range(len_s):\n",
    "            for d in len_w:\n",
    "                end = i+d\n",
    "                if (end <= len_s) and s[i:end] in words:\n",
    "                    intervals.append((i, end))\n",
    "        \n",
    "        if not intervals:\n",
    "            return s\n",
    "        \n",
    "        # print(intervals)\n",
    "        intervals_marged = []\n",
    "        len_intervals = len(intervals)\n",
    "        idx = 1\n",
    "        start, end = intervals[0]\n",
    "        while idx < len_intervals:\n",
    "            cur_s, cur_e = intervals[idx]\n",
    "            if cur_s <= end:\n",
    "                end = max(cur_e, end)\n",
    "            else:\n",
    "                intervals_marged.append((start, end))\n",
    "                start, end = cur_s, cur_e\n",
    "            idx += 1\n",
    "        intervals_marged.append((start, end))\n",
    "\n",
    "        print(intervals,intervals_marged)\n",
    "        \n",
    "        ans = ''\n",
    "        last_e = 0\n",
    "        for start, end in intervals_marged:\n",
    "            ans += s[last_e:start]\n",
    "            ans += '<b>' + s[start:end] + '</b>'\n",
    "            last_e = end\n",
    "        ans += s[last_e:]\n",
    "\n",
    "        return ans\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        def get_nums():\n",
    "            res = []\n",
    "            res = [[i, i+len(word)] for i in range(len(s)) for word in words if s[i:i+len(word)] == word]\n",
    "            print(res)\n",
    "            res.sort(key=lambda s: s[0])\n",
    "            return res\n",
    "        \n",
    "        def combin_nums(res):\n",
    "            s_stack = []\n",
    "            print(\"res\", res)\n",
    "            for s in res:\n",
    "                if not s_stack: s_stack.append(s)\n",
    "                else:\n",
    "                    print(\"t\", s_stack, s)\n",
    "                    if s_stack[-1][1] < s[0]: s_stack.append(s)\n",
    "                    else:\n",
    "                        s_stack[-1][1] = max(s_stack[-1][1], s[1])\n",
    "            print(s_stack)\n",
    "            return s_stack\n",
    "\n",
    "        get_nums_res = get_nums()\n",
    "        combin_nums_res = combin_nums(get_nums_res)\n",
    "        res = list(s)\n",
    "\n",
    "        for i in combin_nums_res[::-1]:\n",
    "            res.insert(i[1], \"</b>\")\n",
    "            res.insert(i[0], \"<b>\")\n",
    "        return \"\".join(res)\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        def get_nums():\n",
    "            res = []\n",
    "            \n",
    "            res = [[i, i+len(word)] for i in range(len(s)) for word in words if s[i:i+len(word)] == word]\n",
    "            print(res)\n",
    "            res.sort(key=lambda s: s[0])\n",
    "            return res\n",
    "        \n",
    "        def combin_nums(res):\n",
    "            s_stack = []\n",
    "            print(\"res\", res)\n",
    "            for s in res:\n",
    "                if not s_stack: s_stack.append(s)\n",
    "                else:\n",
    "                    print(\"t\", s_stack, s)\n",
    "                    if s_stack[-1][1] < s[0]: s_stack.append(s)\n",
    "                    else:\n",
    "                        s_stack[-1][1] = max(s_stack[-1][1], s[1])\n",
    "            print(s_stack)\n",
    "            return s_stack\n",
    "\n",
    "        get_nums_res = get_nums()\n",
    "        combin_nums_res = combin_nums(get_nums_res)\n",
    "        res = list(s)\n",
    "\n",
    "        for i in combin_nums_res[::-1]:\n",
    "            res.insert(i[1], \"</b>\")\n",
    "            res.insert(i[0], \"<b>\")\n",
    "        return \"\".join(res)\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "\n",
    "        def kmp(s, t):\n",
    "\n",
    "            def get_next(t):\n",
    "                N = len(t)\n",
    "                ans = [0] * N \n",
    "                i, j = 0, 1\n",
    "                while j < N:\n",
    "                    if t[j] == t[i]:\n",
    "                        ans[j] = i+1\n",
    "                        j += 1\n",
    "                    else:\n",
    "                        if i > 0:\n",
    "                            i = ans[i-1]\n",
    "                        else:\n",
    "                            ans[j] = 0\n",
    "                            j += 1\n",
    "                return ans\n",
    "            \n",
    "            next = get_next(t)\n",
    "            i, j = 0, 0\n",
    "            M = len(s)\n",
    "            N = len(t)\n",
    "            ans = []\n",
    "            while i < M:\n",
    "                if s[i] == t[j]:\n",
    "                    if j == N-1:\n",
    "                        ans.append([i-N+1, i])\n",
    "                        j = 0\n",
    "                        i = i-N+2\n",
    "                    else:\n",
    "                        i += 1\n",
    "                        j += 1\n",
    "                else:\n",
    "                    if j > 0:\n",
    "                        j = next[j-1]\n",
    "                    else:\n",
    "                        i += 1\n",
    "            return ans\n",
    "        \n",
    "        candidates = []\n",
    "        for t in words:\n",
    "            candidates.extend(kmp(s, t))\n",
    "        if len(candidates) == 0:\n",
    "            return s \n",
    "        candidates = sorted(candidates, key=lambda x: x[0])\n",
    "        cur = candidates[0]\n",
    "        ans = []\n",
    "        for i in range(1, len(candidates)):\n",
    "            c = candidates[i]\n",
    "            if c[0] > cur[1] + 1:\n",
    "                ans.append([cur[0], cur[1]])\n",
    "                cur = c \n",
    "            else:\n",
    "                cur[1] = max(cur[1], c[1])\n",
    "        ans.append([cur[0], cur[1]])\n",
    "        res = ''\n",
    "        start = 0\n",
    "        for a in ans:\n",
    "            res += s[start:a[0]]\n",
    "            res += '<b>'\n",
    "            res += s[a[0]:a[1]+1]\n",
    "            res += '</b>'\n",
    "            start = a[1] + 1\n",
    "        res += s[start:]\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_substring_ranges(self, s, word):\n",
    "        \n",
    "        ans = []\n",
    "        m = len(word)\n",
    "        for i in range(len(s)):\n",
    "            if s[i] != word[0]:\n",
    "                continue\n",
    "            if s[i:i+m] == word:\n",
    "                ans.append([i, i+m])\n",
    "        return ans\n",
    "\n",
    "    def merge_range(self, ranges):\n",
    "        ans = []\n",
    "\n",
    "        ranges.sort(key=lambda x: (x[0], x[1]))\n",
    "        for r in ranges:\n",
    "            if not ans:\n",
    "                ans.append(r)\n",
    "                continue\n",
    "            a = ans.pop()\n",
    "\n",
    "            if r[0] > a[1]:\n",
    "                ans.append(a)\n",
    "                ans.append(r)\n",
    "            else:\n",
    "                ans.append([a[0], max(a[1], r[1])])\n",
    "\n",
    "\n",
    "        return ans\n",
    "\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        ranges = []\n",
    "        for word in words:\n",
    "            ranges += self.get_substring_ranges(s, word)\n",
    "        \n",
    "        merged_ranges = self.merge_range(ranges)\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        bold_string_start = \"<b>\"\n",
    "        bold_string_end = \"</b>\"\n",
    "\n",
    "        index = 0\n",
    "        for r in merged_ranges:\n",
    "            if r[0] != 0:\n",
    "                ans.append(s[index: r[0]])\n",
    "            ans.append(bold_string_start)\n",
    "            ans.append(s[r[0]: r[1]])\n",
    "            ans.append(bold_string_end)\n",
    "            index = r[1]\n",
    "        \n",
    "        if index < len(s):\n",
    "            ans.append(s[index:])\n",
    "        \n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "\n",
    "        starts = []\n",
    "\n",
    "        def helper(a):\n",
    "            return a[0], -a[1]\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            for w in words:\n",
    "                if i + len(w) <= len(s) and s[i:i+len(w)] == w:\n",
    "                    starts.append((i, 1))\n",
    "                    starts.append((i + len(w), -1))\n",
    "        \n",
    "        res = \"\"\n",
    "        cur = 0\n",
    "        starts.sort(key=helper)\n",
    "        \n",
    "        i = 0\n",
    "\n",
    "        for start in starts:\n",
    "            while i < start[0]:\n",
    "                res += s[i]\n",
    "                i += 1\n",
    "\n",
    "            cur += start[1]\n",
    "            if start[1] == 1 and cur == 1:\n",
    "                res += \"<b>\"\n",
    "            elif cur == 0:\n",
    "                res += \"</b>\"\n",
    "        \n",
    "        while i < len(s):\n",
    "            res += s[i]\n",
    "            i += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "\n",
    "        starts = []\n",
    "\n",
    "        def helper(a):\n",
    "            return a[0], -a[1]\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            for w in words:\n",
    "                if i + len(w) <= len(s) and s[i:i+len(w)] == w:\n",
    "                    starts.append((i, 1))\n",
    "                    starts.append((i + len(w), -1))\n",
    "        \n",
    "        res = \"\"\n",
    "        cur = 0\n",
    "        starts.sort(key=helper)\n",
    "        print(starts)\n",
    "        i = 0\n",
    "\n",
    "        for start in starts:\n",
    "            while i < start[0]:\n",
    "                res += s[i]\n",
    "                i += 1\n",
    "\n",
    "            cur += start[1]\n",
    "            if start[1] == 1 and cur == 1:\n",
    "                res += \"<b>\"\n",
    "            elif cur == 0:\n",
    "                res += \"</b>\"\n",
    "        \n",
    "        while i < len(s):\n",
    "            res += s[i]\n",
    "            i += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addBoldTag(self, s: str, words: List[str]) -> str:\n",
    "        m = {}\n",
    "        for word in words:\n",
    "            for i in range(1, len(word)):\n",
    "                prefix = word[:i]\n",
    "                if prefix not in m:\n",
    "                    m[prefix] = False\n",
    "            m[word] = True\n",
    "\n",
    "        n = len(s)\n",
    "        bold = [False] * n\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n + 1):\n",
    "                substr = s[i: j]\n",
    "                if substr not in m:\n",
    "                    break\n",
    "                if m[substr]:\n",
    "                    for k in range(i, j):\n",
    "                        bold[k] = True\n",
    "\n",
    "        ret = ''\n",
    "        inbold = False\n",
    "        for i in range(n):\n",
    "            if bold[i] and not inbold:\n",
    "                ret += '<b>'\n",
    "                inbold = True\n",
    "            elif not bold[i] and inbold:\n",
    "                ret += '</b>'\n",
    "                inbold = False\n",
    "            ret += s[i]\n",
    "        if inbold:\n",
    "            ret += '</b>'\n",
    "        return ret"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
